
// 712.两个字符串的最小ASCII删除和
class Solution {
public:
    int minimumDeleteSum(string s1, string s2) {
        // 此题直接求删除和不好求 , 可以使用正难则反 
        // 但是可以通过求两个字符串的相同字符序列的ASCII码和

        // 使用动态规划来完成 : dp[i][j] 表示 s1[1,i]和s2[1,j]中字符序列的ASCII和
        int n = s1.size() , m = s2.size();
        s1 = " " + s1 , s2 = " " + s2;

        vector<vector<int>> dp(n + 1 ,vector<int>(m + 1));

        for(int i = 1 ; i <= n ; i++)
        {
            for(int j = 1; j <= m ; j++)
            {
                if(s1[i] == s2[j]) dp[i][j] = dp[i - 1][j - 1] + s1[i];
                else dp[i][j] = max(dp[i - 1][j] , dp[i][j - 1]);
            }
        } 
        
        int sum = 0;
        for(int i = 1 ; i <= n || i <=m ; i++)
        {
            if(i <= n ) sum += s1[i];
            if(i <= m ) sum += s2[i];
        }
        return sum - 2*dp[n][m];
    }
};